import java.util.*;
public class test {
    //leetcode 494.目标和(暴搜双解法)
    // 回溯法->暴力搜索
    public int num = 0;
    public int sum = 0;
    public int count = 0;

    public int findTargetSumWays(int[] nums, int target) {
        count = target;
        //dfs(nums, 0);
        dfs1(nums,0,0);
        return sum;
    }
    // 使用全局变量
    public void dfs(int[] nums, int index) {
        if (index == nums.length) {
            if (num == count) {
                sum++;
            }
            return;
        }
        // 1. 加
        num += nums[index];
        dfs(nums, index + 1);
        // 2. 恢复现场(回溯)
        num -= nums[index];
        // 3. 减
        num -= nums[index];
        dfs(nums, index + 1);
        num += nums[index];
    }
    // 不使用全局变量
    public void dfs1(int[] nums,int index,int n){
        if(index == nums.length){
            if(n == count){
                sum++;
            }
            return;
        }
        n += nums[index];
        dfs1(nums,index + 1,n);
        n -= nums[index];
        n -= nums[index];
        dfs1(nums,index + 1,n);
        n += nums[index];
    }
    //leetcode 39.组合总和
    class Solution {
        public List<List<Integer>> list;
        public List<Integer> path;
        public int count;
        public List<List<Integer>> combinationSum(int[] nums, int target) {
            list = new ArrayList<>();
            path = new ArrayList<>();
            count = target;
            //数组,下表,当前路径总和
            dfs(nums,0,0);
            return list;
        }
        public void dfs(int[] nums,int index,int sum){
            if(sum == count){
                list.add(new ArrayList<>(path));
                return;
            }
            // 剪枝1. 防止传入相同组合
            for(int i = index;i < nums.length;i++){
                //传入值都 > 0,如果中途sum > count,则此组合无意义,直接break;
                if(sum > count){
                    break;
                }
                // 剪枝2. 当index越界,此次查找结束,break;
                if(index == nums.length){
                    break;
                }
                path.add(nums[i]);
                dfs(nums,i,sum + nums[i]);
                path.remove(path.size() - 1);
            }
        }
    }
    //leetcode 784.字母大小写全排列
    class Solution {
        public List<String> list;
        public StringBuilder path;

        public List<String> letterCasePermutation(String s) {
            list = new ArrayList<>();
            path = new StringBuilder(s);
            // 字符串,当前访问下标
            dfs(0);
            return list;
        }

        public void dfs(int index) {
            if (index == path.length()) {
                list.add(path.toString());
                return;
            }
            // 如果是字母,进行"修改","不修改"的选择
            // 1. 修改
            char c = path.charAt(index);
            if (Character.isLetter(c)) {
                // 大写改小写
                if (Character.isUpperCase(c)) {
                    path.setCharAt(index, (char) (c + 32));
                } else {
                    // 小写改大写
                    path.setCharAt(index, (char) (c - 32));
                }
                dfs(index + 1);
                // 恢复现场(回溯)
                path.setCharAt(index,c);
            }
            // 2. 不修改
            dfs(index + 1);
        }
    }
}
